﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmExercise.Introduction
{
    /// <summary>
    /// 插入排序
    /// </summary>
    public class InsertionSort
    {
        /// <summary>
        /// 插入排序
        /// </summary>
        public InsertionSort()
        {
            var random = new Random();
            int[] array = new int[100];
            for (int n = 0; n < array.Length; n++)
            {
                array[n] = random.Next(1000);
            }
            // 从第二个数开始，一次与前一个数比较，小就往前
            for (int j = 1; j < array.Length; j++)
            {
                int num = array[j];
                int i = j - 1;
                // 比当前数大、则右移
                while (i >= 0 && array[i] > num)
                {
                    array[i + 1] = array[i];
                    i--;
                }
                array[i + 1] = num;
            }
            array.ToList().ForEach(i => Console.Write($"{i} "));
        }
    }
}
